package code;
import java.util.ArrayList;
import java.util.List;

import models.Tree;
import models.TreeNode;

public class FindPath {
    public ArrayList<ArrayList<Integer>> re = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

        ArrayList<Integer> pathVal = new ArrayList<>();
        int sum=0;
        if(root==null){
            return this.re;
        }
        else {
            letsFindPath(pathVal,sum, root,target);
        }
        return this.re;
    }

    void letsFindPath(ArrayList<Integer> pathVal, int sum, TreeNode root,int target){
        if(root.left == null && root.right==null){
            sum = sum + root.val;
            pathVal.add(root.val);
            ArrayList<Integer> now = new ArrayList<Integer>();
            for(Integer in : pathVal){
                now.add(in);
            }
            if(sum == target){
                if(this.re.size()==0){
                    this.re.add(now);
                }
                else {
                    int i;
                    for(i=0;i<this.re.size();i++){
                        if(this.re.get(i).size()<pathVal.size()){
                            this.re.add(i,now);
                            break;
                        }
                    }
                    if(i == this.re.size()){
                        this.re.add(now);
                    }
                }
            }
        }
        else {
            sum = sum + root.val;
            pathVal.add(root.val);
        }
        if(root.left!=null){
            letsFindPath(pathVal,sum, root.left,target);
        }
        if(root.right!=null){
            letsFindPath(pathVal,sum, root.right,target);
        }
        pathVal.remove(pathVal.size()-1);
    }

    public static void main(String[] args) {
        Tree mytree = new Tree();
        mytree.dataString = new String[]{"10","5","12","4","7"};
        TreeNode root = mytree.creatTreeNode();
        FindPath findPath = new FindPath();
        findPath.FindPath(root,22);
    }
}
